RmbRT Compiler: Mergeable scopes

In the RmbRT programming language, each file has to form a self-contained abstract syntax tree (AST). When including a file from another file, the included file's source is not simply pasted into the including file, but the included file's AST is joined to the including file's AST. Note that this only a one-way relationship: the included file's AST cannot reference the including file's AST, unless it also includes the including file. This mechanic is a huge improvement over languages such as C and C++, where circular includes are impossible due to implementing includes via source code pasting. But it's not trivial to meaningfully join a tree to another tree, especially if the same mechanism is supposed to allow circular includes.

If file A includes another file B, then A's scopes belonging to elements also found in B (such as namespaces with the same name) must include B's equivalent scopes. Scopes are now not just a dictionary of elements, but additionally also point to other scopes they (even transitively) include:

[Name: TYPE; Elem: TYPE] Scope
{
    // This scope's elements coming from this file only.
    Elements: std::[Name; Elem]AutoMap;
    // All (transitively) included scopes coming only from other files.
    IncludedScopes: THIS \ - std::NatSet;

    THIS[n: Name]: Elem *
    {
        IF(e ::= Elements.find(n))
            = e;
        FOR(scope ::= IncludedScopes.start(); scope; ++scope)
            // Careful: do NOT use (*scope!)[n]!
            IF(e ::= scope!->Elements.find(n))
                = e;
        = NULL;
    }
}

Each file has one global scope:

File { GlobalScope: std::[Identifier; Global-std::Dyn]AutoMap; }

Now, it's not sufficient to just join two files' GlobalScopes; we also need to recursively traverse both file's syntax trees in parallel and have them include their counterparts, if they exist. For that, we need Elem to support an include() function that receives the included AST's corresponding element. Note that some elements cannot be merged, such as variables. In that case, an error occurs and the program is invalid.